package lanqiao;

public class dp01 {
    static int[][] dp;
    public static int knapsack(int n, int W, int[] weights, int[] values) {
        // 初始化二维数组dp，大小为(n+1) x (W+1)
         dp = new int[n + 1][W + 1];

        // 填充dp数组
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= W; j++) {
                if (weights[i - 1] > j) {
                    // 如果当前物品重量大于背包容量，不能选择这个物品
                    dp[i][j] = dp[i - 1][j];
                } else {
                    // 选择是否包含当前物品，取两者中的较大值
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]);
                }
            }
        }

        // 返回结果，即dp[n][W]，表示在考虑所有物品且背包容量为W的情况下可以获得的最大价值
        return dp[n][W];
    }

    public static void main(String[] args) {
        // 示例使用
        int n = 3;  // 物品数量
        int W = 20; // 背包容量
        int[] weights = {2, 3, 5}; // 物品重量
        int[] values = {10, 20, 30}; // 物品价值

        int maxValue = knapsack(n, W, weights, values);
        System.out.println("以下为动态规划表");
        for (int[] ints : dp) {
            for (int i : ints) {
                System.out.print(i + "\t");
            }
            System.out.println();
        }
        System.out.println("最大价值是: " + maxValue);
    }
}
